//=============================================================================
///	Hash table
//=============================================================================

#include "hashtable.h"
#include <string.h>		// for memset
#include <assert.h>

#ifndef	FALSE
#define	FALSE	(0)
#define	TRUE	(1)
#endif


static __inline void _add2buf(HashEntry** buf, size_t siz, HashEntry* p) {
	unsigned int idx = p->hash % siz;
	p->next = buf[idx];
	buf[idx] = p;
}

static void _move_entries_to_newbuf(HashEntry** newbuf, size_t newsiz, HashEntry** oldbuf, size_t oldsiz) {
	// Re-indexing
	size_t i;
	for (i=0; i<oldsiz; ++i) {
		HashEntry* p = oldbuf[i];
		while (p != NULL) {
			HashEntry* next = p->next;
			_add2buf(newbuf, newsiz, p);
			p = next;
		}
	}
}

void ht_init(HashTable* ht, const HashVTbl* vtbl) {
	ht->vtbl = vtbl;
	ht->buf = NULL;
	ht->bufsiz = 0;
}

void ht_term(HashTable* ht) {
	ht_resize(ht, 0);
}

void ht_clear_all(HashTable* ht) {
	size_t siz = ht->bufsiz, i;
	for (i=0; i<siz; ++i) {
		HashEntry* p = ht->buf[i];
		ht->buf[i] = NULL;
		while (p != NULL) {
			HashEntry* next = p->next;
			(ht->vtbl->free)(p);
			p = next;
		}
	}
}

void ht_resize(HashTable* ht, unsigned int siz) {
	if (siz > 0) {
		size_t bytesiz = sizeof(HashEntry*) * siz;
		HashEntry** newbuf = (HashEntry**)(ht->vtbl->alloc)(bytesiz);
		assert(newbuf != NULL);
		memset(newbuf, 0x00, bytesiz);

		if (ht->bufsiz > 0) {
			_move_entries_to_newbuf(newbuf, siz, ht->buf, ht->bufsiz);
			(ht->vtbl->free)(ht->buf);
		}

		ht->buf = newbuf;
		ht->bufsiz = siz;
	} else {
		ht_clear_all(ht);

		(ht->vtbl->free)(ht->buf);
		ht->buf = NULL;
		ht->bufsiz = 0;
	}
}

HashEntry* ht_find(HashTable* ht, const void* key) {
	if (ht->bufsiz > 0) {
		unsigned int hash_key = (ht->vtbl->hash)(key);
		unsigned int idx = hash_key % ht->bufsiz;
		HashEntry* p;
		for (p = ht->buf[idx]; p != NULL; p = p->next) {
			if (p->hash == hash_key && (ht->vtbl->check)(p->key, key)) {
				return p;
			}
		}
	}
	return NULL;
}

int ht_remove(HashTable* ht, const void* key) {
	if (ht->bufsiz > 0) {
		unsigned int hash_key = (ht->vtbl->hash)(key);
		unsigned int idx = hash_key % ht->bufsiz;
		HashEntry *p, *q;
		for (p = ht->buf[idx], q = NULL; p != NULL; q = p, p = p->next) {
			if (p->hash == hash_key && (ht->vtbl->check)(p->key, key)) {
				// find: remove entry
				if (q != NULL) {
					q->next = p->next;
				} else {
					ht->buf[idx] = p->next;
				}
				(ht->vtbl->free)(p);
				return TRUE;
			}
		}
	}
	return FALSE;
}

void ht_add_direct(HashTable* ht, const void* key, void* val) {
	HashEntry* p;
	assert(ht->bufsiz > 0);

	p = (ht->vtbl->alloc)(sizeof(*p));
	assert(p != NULL);
	p->hash = (ht->vtbl->hash)(key);
	p->key = key;
	p->val = val;
	_add2buf(ht->buf, ht->bufsiz, p);
}


HashEntry* ht_begin(HashIterator* it, HashTable* ht) {
	it->ht = ht;
	it->idx = -1;
	it->p = NULL;
	return ht_next(it);
}

HashEntry* ht_next(HashIterator* it) {
	HashEntry* p = it->p;
	if (p != NULL) {
		p = p->next;
	}
	if (p == NULL) {
		HashTable* ht = it->ht;
		unsigned int bufsiz = ht->bufsiz;
		unsigned int idx;
		for (idx = it->idx; ++idx < bufsiz; ) {
			p = ht->buf[idx];
			if (p != NULL)	break;
		}
		it->idx = idx;
	}
	it->p = p;
	return p;
}






void ht_get_info(HashTable* ht, int* psize, int* pelem, int* pcollide, int* pmaxcollide) {
	int elem = 0, collide = 0, maxcollide = 0;
	unsigned int i, num = ht->bufsiz;
	*psize = num;
	for (i=0; i<num; ++i) {
		int n = 0;
		HashEntry* p;
		for (p = ht->buf[i]; p != NULL; p = p->next) {
			++n;
		}
		elem += n;
		if (n > 1) {
			++collide;
			p = ht->buf[i];
		}
		if (maxcollide < n)	maxcollide = n;
	}
	*pelem = elem;
	*pcollide = collide;
	*pmaxcollide = maxcollide;
}

